package mySort;
import java.util.Stack;
//快速排序非递归
public class QuickSortNor {

    //默认挖坑法
    public int partitionHole(int[] arr, int left, int right) {
        int pivot = left;
        //有效区间元素个数需要大于1，所以这里不能是等于
        while (left < right) {
            while (left < right && arr[right] >= arr[pivot]) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= arr[pivot]) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = arr[pivot];
        return left;
    }

    public int threeOfMid(int[] arr, int left, int right) {
        int mid = left + (right-left)>>>1;
        if(arr[left] < arr[right]) {
            if(arr[mid] < arr[left]) {
                return left;
            }else if( arr[mid] > arr[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(arr[mid] < arr[right]) {
                return right;
            }else if(arr[mid] > arr[left]) {
                return left;
            }else {
                return mid;
            }
        }

    }

    public void quickSort(int[] arr) {
        Stack<Integer> stack = new Stack<>(); //需要用栈来模拟递归的过程
        int left = 0;
        int right = arr.length - 1;

        int index = threeOfMid(arr, left, right);
        swap(arr, index, left); //三数取中

        int pivot = partitionHole(arr, left, right);
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }

        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partitionHole(arr, left, right);
            if (left < pivot - 1) {  //如果这个区间元素个数大于1
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot + 1 < right) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
